﻿module Physics.Chapter5.LookupMap

open System.Collections.Generic

type LookupMap = 
  {
    Entries         : ResizeArray<int>
    ExistingEntries : bool[]
  } with 
      member map.Add v =
        if map.ExistingEntries.[v] |> not then 
          do map.ExistingEntries.[v] <- true
          do map.Entries.Add v
      member map.Clear() =
        for i in map.Entries do
          map.ExistingEntries.[i] <- false
        map.Entries.Clear()
      member map.Length = map.ExistingEntries.Length

let mutable private cached_lookup_maps : (ResizeArray<int * Stack<LookupMap>>)[] = 
  [|
    for i = 0 to 55 do
      yield ResizeArray()
  |]

let rec private push lm =
  let cache_column = cached_lookup_maps.[(lm.ExistingEntries.Length / 10) % cached_lookup_maps.Length]
  match cache_column |> Seq.tryFind (fun (l,_) -> l = lm.Length) with
   | Some(_,cache_line) ->
     cache_line.Push lm
   | _ ->
     let stack = Stack()
     stack.Push lm
     cache_column.Add(lm.Length,stack)

and private try_find length = 
  let cache_column = cached_lookup_maps.[(length / 10) % cached_lookup_maps.Length]
  if cache_column.Count = 0 then
    None
  else
    match cache_column |> Seq.tryFind (fun (l,_) -> l = length) with
    | Some(_,cache_line) -> 
      if cache_line.Count = 0 then
        None
      else
        Some(cache_line.Pop())
    | None -> None

//let mutable miss_cnt = 0
//let mutable hit_cnt = 0

type LookupMap
  with
    static member Delete(lm:LookupMap) =
      do push lm
    static member Create(length:int) = 
      let mk_new() =
//        miss_cnt <- miss_cnt + 1
//        if miss_cnt % 100 = 0 then
//          printfn "miss/hit %d/%d" miss_cnt hit_cnt
        {
          Entries         = ResizeArray(length / 4)
          ExistingEntries = [| for i = 0 to length - 1 do yield false |]
        }
      match try_find length with
      | Some l -> 
//        hit_cnt <- hit_cnt + 1
        l.Clear()
        l
      | _ ->
        mk_new()

